Surfaces are important in research disciplines like Computer-Aided Design (CAD), Computer-Aided Engineering (CAE), Computational Geometry and Computer Graphics.
Computer-Aided Design is the modeling of physical systems on computers, allowing both interactive and automatic analysis of design variants, and the expression of designs in a form suitable for manufacturing. It results from the development of a wide range of computer-based tools assisting in the design and creation of products and goods. These computerized tools help, amongst others, engineers and architects in their design and modeling activities of detailed two- or three-dimensional models of physical objects, such as mechanical parts, buildings, and molecules. In Computer-Aided Design, the focus lies on construction and design of curves and surfaces.
Computer-Aided Engineering (CAE) analysis is the application of computer software in engineering to analyze the robustness and performance of components and assemblies of mechanical parts. It encompasses analysis and manufacturing simulation, validation and optimization of products and are considered as computerized manufacturing tools.
Computational Geometry is the study of (computer) algorithms to solve problems stated in terms of geometry. Computational geometry has recently expanded its scope to include curves and surfaces.
Computer Graphics is the research field dedicated to visualization, where one utilizes computers both to generate visual images and to alter visual and spatial information sampled from the real world. Emphasis lies on visualization and output of surfaces.
Irrespective of the purpose for which the surface is used, a computer system requires a suitable representation of the surface. A surface representation is the formulation of a surface such that a human is able to reason about the surface with the aid of a computer and to apply queries on the surfaces according to the application requirements. Many representations have been proposed each with different advantages and disadvantages. Conversions between representations are needed in order to be able to use the advantages of different representations in the same application. For instance, piecewise linear approximations in the form of meshes are regularly used for visualization and further geometric processing. Often it is not possible to give a representation that defines the same surface as the original surface; in such cases, the surface is approximated.
Meshing is an essential representation for 3D general geometric models. Meshing is a software technique for dividing a 2D/3D shape into a set of elementary elements, commonly in the form of triangular or quadrilateral elements.
Meshing is an integral part of the CAE analysis process. The mesh influences the accuracy, convergence and speed of the solution. More importantly, the time it takes to create a mesh model is often a significant portion of the time it takes to get results from a CAE solution. Therefore, the better and more automated and accurate the meshing tools, the better the solution.
Meshing has received a great deal of attention from researchers in a variety of fields, ranging from CDA through numerical analysis to Computational Geometry. A high quality mesh is required for visualization, modeling, numerical analysis and manufacturing. The quality of a mesh is measured by the properties of its elements, i.e., triangles or quads, which should be as regular as possible. That is, the shape, angles or size of these elements must satisfy certain geometrical and mechanical physical criteria. Current meshing methods are applied on 3D genus-g objects. Curvature is the main geometrical criterion. However, size and the part dimensions are also used as geometric criteria.
The results, however, are not satisfactory, so that a remeshing is needed. In most cases, local meshing operations such as 3D edge splitting and merging are performed on the original mesh. Moreover, remeshing by replacing the original mesh elements with other new elements that differ in size and shape can be a difficult task and cannot be applied modularly. That is, changing one of the criteria leads to reactivating the remeshing process from scratch. In addition, the remeshed model is highly dependent on the connectivity of the original mesh and therefore cannot optimize the mesh significantly. In many cases, the original mesh is often highly irregular and non-uniform.
To overcome the above problems, recently researchers have applied mesh mapping from the 3D object domain to the parameterization domain, subsequently remeshing and then mapping back from the parameterization domain into the 3D object domain. For this, a plane is usually used as the simple parameterization domain of a rectangular plane to which the original mesh is mapped and remeshed. Then, the new mesh is mapped from the plane to the 3D object. In most cases, a one-boundary of the closed genus-g object is created and mapped to the boundary of the parameterization plane. Then, the internal mesh vertices are mapped to the plane with respect to the boundary location. Usually, remeshing is applied in the parameterization domain iteratively, using algorithms such as Voronoi diagrams (see Du et al., “Centroidal voronoi tesselation”, Applications and algorithms. SIAM review, 41(4):637-676, 1999) until a desired 2D mesh is achieved. The main problems with these common remeshing approaches are as follows: (a) the remeshing process can be used efficiently only on genus-0 meshes, and (b) replacing the elements, for example from triangles to quads, is not trivial. Therefore, a new approach is required to overcome the above problems.
Parameterization methods have been developed for remeshing but they all present some problems. Until now, research studies have primarily considered planar parameterization with fixed boundaries. For closed meshes that have been cut and flattened, however, planar parameterization suffers from large distortions, especially on meshes whose original genus is greater than zero. The flattening process usually involves a preliminary cutting operation that results in a 1-boundary mesh. Much research has been devoted to finding a cut graph for genus-g class meshes. A cut graph is a connected graph containing 2g loops that are also called generators, where g is the genus. Cutting a genus-g mesh according to a cut graph yields a 1-boundary mesh that is homeomorphic to a disk. This 1-boundary mesh can then be flattened using any planar parameterization method. The parameterization resulting from the above procedure has large distortions, especially near the boundaries. Methods have been disclosed (see Cohen-Or et al., “Bounded-distortion piecewise mesh parameterization”, IEEE Visualization, pp. 355-362, 2002); Desbrun et al., “Intrinsic Parameterizations of Surface Meshes”, Computer Graphics Forum, 21(3), pp. 210-218, 2002; Sheffer et al., “Parameterization of Faceted Surfaces for Meshing Using Angle Based Flattening”, Engineering with Computers, 17(30, pp. 326-337, 2001; Yoshizawa et al., “A fast and simple stretch-minimizing mesh parameterization”, Intl. Conf. On Shape Modeling and Applications, pp. 200-208, June 2004) that can be used to cope with large distortions near the boundaries in high genus objects that are presented as one-boundary surfaces, but in such cases the continuity of the parameterization along the boundary cannot be controlled, nor can the characteristics of the mesh to be preserved. To cope with distortion from cutting the mesh and fixing its boundary, some studies have considered spherical parameterization for genus-0 objects. Gotsman (Gotsman et al., “Fundamentals of Spheric Parameterizations for 3D Meshes”, ACM Trans. on Graphics, 22, 2003) teaches that any positive weights for genus-0 meshes can be used. The result is a spherical parameterization, and the solution is achieved by solving a non-linear system. To reduce distortion, Gu and Yau (“Global Conformal Surface Parameterization”, SGP, pp. 127-137, 2003) have offered a solution for the open problem of conformal parameterization for manifold genus-g meshes. Although different weights can be used over the edges, these weights must be symmetric. That is, in the case of an edge eij with a weight kij, kij must be equal to kji. Thus, neither the mean-value weights nor the shape-preserving weights can be used, nor can any other non-symmetric weight. Furthermore, in Gu and Yau (2003), harmonic weights are used, so that meshes with obtuse angles cannot be handled because such angles will cause the harmonic weights to be negative, in which case the process will converge more slowly and the triangles may overlap. Therefore, if the mesh includes triangles with obtuse angles, it should be remeshed without obtuse angles.
In summary, remeshing of 3D models is important for many CAD, visualization and analysis applications. Current remeshing methods for closed manifold gene-g meshes usually involve 3D mesh operations such as splitting and merfing the mesg edges in order to construct a new mesh that will satisfy given geometrical criteria. These 3D operations are local and usually do not lead to the desired new mesh. Indeed, the remeshed model usually does not satisfy regular criteria. Moreover, changing one of the criteria will not lead to reactivating the remeshing process from scratch.
There is a need in the art for novel remeshing approaches that will overcome the above problems.